package com.tan.collection.sieve;

import java.util.BitSet;

public class Sieve {
    public static void main(String[] args) {
        int n = 2000000;
        //数量定义
        long start = System.currentTimeMillis();
        //开始时间
        BitSet bitSet = new BitSet(n+1);
        //创建一个位集。初始化位集大小为：n+1
        int count = 0;
        //设置一个变量，统计数量。
        int i;
        //设置一个自变量。
        for (i=2;i<=n;i++)
            //遍历循环位集
            bitSet.set(i);
        //把位集设置为“开”的状态。
        i=2;
        while (i*i<=n){
            if (bitSet.get(i)){
                //获取位集状态
                count++;
                //统计数量
                int k =2*i;
                while (k<=n){
                    bitSet.clear(k);
                    k+=i;
                }
            }
            i++;
            //自增
        }
        while (i<=n){
            if (bitSet.get(i))count++;
            i++;
        }
        long end = System.currentTimeMillis();
        System.out.println(count+" primes");
        System.out.println((end - start)+" milliseconds");
    }
}
